package chapter5.section4

/**
 * 单层正则表达式
 * 构造一个Java的正则表达式来描述所有二值字母表的合法正则表达式字符串的集合，字符串不含有嵌套的括号。
 * 例如，(0.*1)*和(1.*0)*都是这个语言中的字符串，但(1(0或者1)1)*不是。
 *
 * 解：这题有几个要求：
 * 1、括号匹配，每个左括号都有对应的右括号，不能只有左括号或右括号
 * 2、括号不能嵌套
 * 3、只匹配最基本的正则表达式，只包含连接、或'|'、闭包'*'、括号'(' ')'、通配符'.'这几个操作，不含其他操作
 * 4、不存在连续的'*'或'|'操作符，'*'或'|'之前必须有1、0、通配符或右括号
 *
 * 设[01\.]+\*?\|?表示一个正则的最小单位X，意思是至少一个数字之后接可选的闭包操作以及可选的或操作
 * 括号的最小单位为\(X+\)\*?\|?，意思是括号内至少有一个X，后面可以接可选的闭包操作以及可选的或操作
 * 完整的正则表达式可以用X表示为(X|\(X+\)\*?\|?)*
 */
fun main() {
    val nfa = NFA("([01\\.]+\\*?\\|?|\\(([01\\.]+\\*?\\|?)+\\)\\*?\\|?)*")
    check(nfa.recognizes("(0.*1)*"))
    check(nfa.recognizes("(1.*0)*"))
    check(nfa.recognizes("10*(0|10*1*)*111"))
    check(nfa.recognizes("0*|(11*0*1*)*(01001|1111|0*)|010|11*0*"))
    check(!nfa.recognizes("(1(0"))
    check(!nfa.recognizes("1)1)*"))
    check(!nfa.recognizes("(1(0|1)1)*"))
    check(!nfa.recognizes("11||0"))
    check(!nfa.recognizes("11|*0"))
    check(!nfa.recognizes("(110*|1010)**"))
    check(!nfa.recognizes("(10*(001|01*))"))

    println("check succeed.")
}